//
// Description: 二分算法 模板
// Created by Loading on 2021/8/1.
//

// 例题：数的范围，https://www.acwing.com/problem/content/description/791/

#include <bits/stdc++.h>

using namespace std;

// 检查 x 是否满足某种性质，T 为 x 的数据类型
template<typename T>
bool check(T x) {
    // 检查……

    return true;
}

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
/* 尽量往左寻找答案，寻找一个区间的左边界，最小XX，最短XX……等 */
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + (r - l >> 1);
        if (check(mid)) {
            r = mid;    // check()判断mid是否满足性质
        } else {
            l = mid + 1;
        }
    }
    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
/* 尽量往右寻找答案，寻找一个区间的右边界，最大XX，最长XX……等 */
int bsearch_2(int l, int r) {
    while (l < r) {
        /* 如果使用 mid = l + ((r - l) >> 1) 可能出现死循环 */
        int mid = l + (r - l + 1 >> 1);
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

// 浮点数二分算法
double bsearch_3(double l, double r) {
    // eps 表示精度，取决于题目对精度的要求
    const double eps = 1e-6;

    while (r - l > eps) {
        /* 浮点数不会取整，无需进行各种 + 1 和 - 1 操作 */
        double mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}

int main() {

}